package algorithm.graph;

import java.util.Vector;

/**@Description 稀疏图:邻接表
 *
 * @author bingo
 *
 * @Date 2018/3/11
 */
public class SparseGraph  implements Graph{

    /**顶点数*/
    private int n;
    /**边数*/
    private int m;
    /**是否为有向图*/
    private boolean directed;

    /**图的具体数据*/
     private Vector<Integer>[] g;

    public SparseGraph(int n,boolean directed) {
        this.n = n;
        this.m = 0;
        this.directed = directed;
        g = (Vector<Integer>[])new Vector[n];
       for(int i=0;i<n;i++){
          g[i] = new Vector<Integer>();
      }
    }

  /**向图中增加一条边*/
    public void addEdge(int v,int w){
        if(hasEdge(v,w)){
            return;
        }

        g[v].add(w);
        if(v != w && !directed){
            g[w].add(v);
        }

    }
/**验证图中是否有从v-w的边*/
    public boolean hasEdge(int v,int w){
        Vector<Integer> vector  =  g[v];
        for(int i=0;i<vector.size();i++){
            if(vector.elementAt(i)==w){

                return  true;
            }
        }
        return false;

    }
    /**返回图中一个顶点的所有邻边*/
    public Iterable<Integer> adj(int v){

        assert v >=0 && v < n;

        return  g[v];
    }

    @Override
    public void show() {

        for(int i=0;i<n;i++){
            System.out.print("vertex " + i + ":\t");
            for(int j=0;j<g[i].size();j++){

                System.out.print(g[i].elementAt(j)+"\t");

            }
            System.out.println();
        }

    }
  /**返回定点数*/
    @Override
    public int n() {
        return n;
    }
 /**返回边数*/
    @Override
    public int m() {
        return m;
    }



}
